|
In set theory, a tree is a partially ordered set (''T'', <) such that for each ''t'' ∈ ''T'', the set is well-ordered by the relation <. Frequently trees are assumed to have only one root (i.e. minimal element), as the typical questions investigated in this field are easily reduced to questions about single-rooted trees. ==Definition== A tree is a partially ordered set (poset) (''T'', <) such that for each ''t'' ∈ ''T'', the set is well-ordered by the relation <. In particular, each well-ordered set (''T'', <) is a tree. For each ''t'' ∈ ''T'', the order type of is called the height of ''t'' (denoted ht(''t'', ''T'')). The height of ''T'' itself is the least ordinal greater than the height of each element of ''T''. A root of a tree ''T'' is an element of height 0. Frequently trees are assumed to have only one root. Trees with a single root in which each element has finite height can be naturally viewed as rooted trees in the sense of graph-theory, or of theoretical computer science: there is an edge from ''x'' to ''y'' if and only if ''y'' is a direct successor of ''x'' (i.e., ''x''<''y'', but there is no element between ''x'' and ''y''). However, if ''T'' is a tree of height > ω, then there is no natural edge relation that will make ''T'' a tree in the sense of graph theory. For example, the set does not have a natural edge relationship, as there is no predecessor to ω. A branch of a tree is a maximal chain in the tree (that is, any two elements of the branch are comparable, and any element of the tree ''not'' in the branch is incomparable with at least one element of the branch). The length of a branch is the ordinal that is order isomorphic to the branch. For each ordinal α, the α-th level of ''T'' is the set of all elements of ''T'' of height α. A tree is a κ-tree, for an ordinal number κ, if and only if it has height κ and every level has size less than the cardinality of κ. The width of a tree is the supremum of the cardinalities of its levels. Single-rooted trees of height ≤ ω forms a meet-semilattice, where meet (common ancestor) is given by maximal element of intersection of ancestors, which exists as the set of ancestors is non-empty and finite well-ordered, hence has a maximal element. Without a single root, the intersection of parents can be empty (two elements need not have common ancestors), for example where the elements are not comparable; while if there are an infinite number of ancestors there need not be a maximal element – for example, where are not comparable. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Tree (set theory)」の詳細全文を読む スポンサード リンク
|